package com.learn.algorithm_322;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;

/**
 *
 * <a href="https://leetcode.cn/problems/coin-change/description/">322. 零钱兑换</a>
 *
 *
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 *
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 *
 * 你可以认为每种硬币的数量是无限的。
 */
public class Solution {

    @Test
    public void test() {
//        int[] coins = {186,419,83,408};
//        int amount = 6249;

        int[] coins = {1,2,5};
        int amount = 11;

        int count = coinChange(coins, amount);
        System.out.println("最少硬币数：" + count);
    }

    /**
     * 动态规划
     * dp方式，从最小数开始计算，避免了重复子问题计算
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        // 初始化数组长度 amount + 1，相当于正无穷，因为硬币数最多不超过amount
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);

        // 金额=0时，硬币数0
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            for (int coin : coins) {
                if (i - coin < 0) {
                    continue;
                }
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }

        int result = dp[amount] == amount + 1 ? -1 : dp[amount];
        return result;
    }

}
